package quicksort;

import java.util.Arrays;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @Author: zhangQi
 * @Date: 2020-09-19 15:05
 */
public class QuickSort {

    public static void main(String[] args) {
        System.out.println(quickSort(Arrays.asList(10,3,5,1,66,2,343,23)));
    }

    private static List<Integer> quickSort(List<Integer> list) {
        if (list.size() < 2) {
            return list;
        } else {
            //recursive case , pivot 支点
            Integer pivot = list.get(0);

            //sub-array of all the elements less than the pivot
            List<Integer> less = list.stream().skip(1).filter(el -> el <= pivot).collect(Collectors.toList());

            //sub-array of all the elements greater than the pivot
            List<Integer> greater = list.stream().skip(1).filter(el -> el > pivot).collect(Collectors.toList());

            //Function.identity return itself
            return Stream.of(quickSort(less).stream(), Stream.of(pivot), quickSort(greater).stream())
                    .flatMap(Function.identity()).collect(Collectors.toList());

        }
    }
}
